package recursion

// https://leetcode-cn.com/problems/generate-parentheses/
// 生成括号组合
// 算法: 递归
// 时间复杂度: O(n)
func GenerateParenthesis(n int) []string {
	retMap := make(map[string]string)
	retArr := make([]string, 0)
	recurForParenthesis(retMap, "", 0, 0, 0, n)
	for currentParenthesis := range retMap {
		retArr = append(retArr, currentParenthesis)
	}
	return retArr
}

// 直接递归，限制: 右括号的前面必须有足够的左括号
func recurForParenthesis(retMap map[string]string, currentParenthesis string,
	leftCount, rightCount, leftLeftCount, limitCount int) {
	// 放左括号: 只需要判断是否还有空闲的左括号即可
	if leftCount < limitCount {
		recurForParenthesis(retMap, currentParenthesis+"(",
			leftCount+1, rightCount, leftLeftCount+1, limitCount)
	}
	// 放右括号: 需要左边至少有一个需要匹配的左括号
	if rightCount < limitCount && leftLeftCount > 0 {
		// 放右括号之后还需要额外判断是否已经到最终答案了
		if rightCount+1 == limitCount && leftCount == limitCount {
			retMap[currentParenthesis+")"] = "1"
		} else {
			recurForParenthesis(retMap, currentParenthesis+")",
				leftCount, rightCount+1, leftLeftCount-1, limitCount)
		}
	}
}
